package baseclass.e_tree;


import utils.TreeNode;
import utils.TreeUtil;

import java.util.LinkedList;
import java.util.Queue;
import java.util.Stack;

/**
 * @date 2020/2/29 15:26
 */
public class Code11_ReverseBT {
    //in order recursion
    public static void process1(TreeNode root){
        if(root == null) return;
        //change left and right for each node
        TreeNode temp = root.left;
        root.left = root.right;
        root.right = temp;
        //no mater visited who first
        if(root.left != null)
            process1(root.left);
        if(root.right != null)
            process1(root.right);
    }
    // in order iterator
    public static void process2(TreeNode root){
        Stack<TreeNode> stack = new Stack<>();
        stack.push(root);
        while(!stack.isEmpty()){
            root = stack.pop();
            //change the link
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            //reverse in order,no matter who goes first
            if(root.right != null){
                stack.push(root.right);
            }
            if(root.left != null){
                stack.push(root.left);
            }

        }
    }
    // level traverse
    public static void process3(TreeNode root){
        Queue<TreeNode> queue = new LinkedList<>();
        queue.add(root);
        while(!queue.isEmpty()){
            root = queue.poll();
            //change the  node
            TreeNode temp = root.left;
            root.left = root.right;
            root.right = temp;
            if(root.right != null){
                queue.add(root.right);
            }
            if(root.left != null){
                queue.add(root.left);
            }
        }
    }

    public static void main(String[] args) {
        TreeNode head = new TreeNode(1);
        head.left = new TreeNode(2);
        head.right = new TreeNode(3);
        head.left.left = new TreeNode(4);
        head.left.right = new TreeNode(5);
        head.right.left = new TreeNode(6);
        head.right.right = new TreeNode(7);

        TreeUtil.printTree(head);
        process2(head);
        TreeUtil.printTree(head);
    }

}
